|
In graph theory, the perfect graph theorem of states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by , and it is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem〔This was also conjectured by Berge but only proven much later by .〕 characterizing perfect graphs by their forbidden induced subgraphs. ==Theorem statement== A perfect graph is an undirected graph with the property that, in every one of its induced subgraphs, the size of the largest clique equals the minimum number of colors in a coloring of the subgraph. Perfect graphs include many important graphs classes including bipartite graphs, chordal graphs, and comparability graphs. The complement of a graph has an edge between two vertices if and only if the original graph does not have an edge between the same two vertices. Thus, a clique in the original graph becomes an independent set in the complement and a coloring of the original graph becomes a clique cover of the complement. The perfect graph theorem states: :The complement of a perfect graph is perfect. Equivalently, in a perfect graph, the size of the maximum independent set equals the minimum number of cliques in a clique cover. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「perfect graph theorem」の詳細全文を読む スポンサード リンク
|